#include <string>
#include <unordered_map>
#include <iostream>
#include <vector>
using namespace std;
//class Solution {
//public:
//    string minWindow(string s, string t)
//    {
//        if (s.size() < t.size())
//        {
//            return "";
//        }
//        string ret;
//        int value_count = 0;
//        unordered_map<char, int> hash_st;
//        unordered_map<char, int> hash_s;
//
//        for (auto& e : t)
//        {
//            hash_st[e]++;
//        }
//
//        int left = -1;
//        int right = 0;
//        while (right < s.size())
//        {
//            hash_s[s[right]]++;
//            if (hash_st.count(s[right]) && hash_s[s[right]] <= hash_st[s[right]])
//            {
//                value_count++;
//            }
//
//            if (value_count == t.size())
//            {
//                while (value_count == t.size())
//                {
//                    hash_s[s[++left]]--;
//                    if (hash_st.count(s[left]) && hash_s[s[left]] < hash_st[s[left]])
//                    {
//                        value_count--;
//                    }
//                }
//                if (ret.size() == 0)
//                {
//                    ret = string(s.begin() + left, s.begin() + right + 1);
//                }
//                ret = ret.size() < (right - left + 1) ? ret : string(s.begin() + left, s.begin() + right + 1);
//
//            }
//            right++;
//        }
//
//        return ret;
//    }
//};
//
//int main()
//{
//    Solution().minWindow("cabwefgewcwaefgcf", "cae");
//}

class Solution {
public:
    enum direction
    {
        RIGHT,
        DOWN,
        LEFT,
        UP
    };

    vector<int> spiralOrder(vector<vector<int>>& matrix)
    {
        vector<int> ret;
        direction dire = RIGHT;
        vector<vector<bool>> hash(matrix.size(), vector<bool>(matrix[0].size(), false));
        int i = 0, j = 0;
        int row = matrix.size();
        int col = matrix[0].size();
        int total = matrix.size() * matrix[0].size();

        int size = 0;
        while (1)
        {
            size = ret.size();
            if (ret.size() == total)
            {
                break;
            }
            
            if (dire == RIGHT)
            {
                if (j < col && hash[i][j] == false)
                {
                    hash[i][j] = true;
                    ret.push_back(matrix[i][j]);
                    j++;
                }
                else
                {
                    i++;
                    j--;
                    dire = DOWN;
                }
            }
            else if (dire == DOWN)
            {
                if (i < row && hash[i][j] == false)
                {
                    hash[i][j] = true;
                    ret.push_back(matrix[i][j]);
                    i++;
                }
                else
                {
                    j--;
                    i--;
                    dire = LEFT;
                }
            }
            else if (dire == LEFT)
            {
                if (j >= 0 && hash[i][j] == false)
                {
                    hash[i][j] = true;
                    ret.push_back(matrix[i][j]);
                    j--;
                }
                else
                {
                    i--;
                    j++;
                    dire = UP;
                }
            }
            else 
            {
                if (hash[i][j] == false)
                {
                    hash[i][j] = true;
                    ret.push_back(matrix[i][j]);
                    i--;
                }
                else
                {
                    j++;
                    i++;
                    dire = RIGHT;
                }
            }
        }


        return ret;
    }
};

int main()
{
    vector<vector<int>> matrix = {{ 1,2,3,4 }, { 5, 6, 7, 8 },{ 9, 10, 11, 12 }};
    Solution().spiralOrder(matrix);
    return 0;
}